package com.leetcode.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * leetcode 329 矩阵中的最长递增路径
 */
public class Solution329 {
    private static class Pair {
        int value;
        int level;
        int row;
        int column;


        public Pair(int value, int level, int row, int column) {
            this.value = value;
            this.level = level;
            this.row = row;
            this.column = column;
        }
    }

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int max = 0;
        int[][] memory = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int tmp = bfs(matrix, i, j, memory);
                if (max < tmp) {
                    max = tmp;
                }
            }
        }

        return max;
    }

    private int bfs(int[][] matrix, int row, int column, int[][] memory) {
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(matrix[row][column], 1, row, column));
        Pair pair = queue.peek();
        int result = 0;
        while (!queue.isEmpty()) {
            pair = queue.poll();
            if (memory[pair.row][pair.column] != 0) {
                result = Math.max(result, pair.level + memory[pair.row][pair.column] - 1);
                continue;
            }
            // 上
            if (pair.row - 1 >= 0 && matrix[pair.row-1][pair.column] > pair.value) {
                queue.offer(new Pair(matrix[pair.row-1][pair.column], pair.level + 1, pair.row - 1, pair.column));
            }
            // 下
            if (pair.row + 1 < matrix.length && matrix[pair.row+1][pair.column] > pair.value) {
                queue.offer(new Pair(matrix[pair.row+1][pair.column], pair.level + 1, pair.row + 1, pair.column));
            }
            // 左
            if (pair.column - 1 >= 0 && matrix[pair.row][pair.column-1] > pair.value) {
                queue.offer(new Pair(matrix[pair.row][pair.column-1], pair.level + 1, pair.row, pair.column - 1));
            }
            // 右
            if (pair.column + 1 < matrix[pair.row].length && matrix[pair.row][pair.column+1] > pair.value) {
                queue.offer(new Pair(matrix[pair.row][pair.column+1], pair.level + 1, pair.row, pair.column + 1));
            }
        }
        memory[row][column] = Math.max(pair.level, result);
        return memory[row][column];
    }

    public static void main(String[] args) {
        Solution329 solution329 = new Solution329();
        int[][] matrix = new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        System.out.println(solution329.longestIncreasingPath(matrix));
    }
}
